Năm 2010, Nguyễn Trường Tô được dư luận biết đến qua vụ án mua dâm nữ sinh dưới 18 tuổi. Sự kiện bắt đầu vào tháng 1/2006, khi Công an thị xã Hà Giang bắt được một gái bán dâm có giữ trong điện thoại một số hình ảnh được cho là của ông Tô trong tư thế không quần áo, do cô ta chụp lại bằng điện thoại di động sau khi hai người "quan hệ" cuối năm 2005.[2] Đến cuối năm 2009, vụ án bắt đầu với sự bắt giam ông Sầm Đức Xương (50 tuổi), khi đó là Hiệu trưởng Trung học phổ thông Việt Lâm, huyện Vị Xuyên tỉnh Hà Giang, đã tổ chức đường dây mua dâm nữ sinh trường này phục vụ nhiều người trong đó có ông Tô.[3] Tuy nhiên sau đó các cơ quan tố tụng Hà Giang cho rằng không đủ cơ sở để xem xét xử lý trách nhiệm hình sự những người đó về hành vi mua dâm người chưa thành niên.[4]

Theo đó ngày 5/7/2010, Ủy ban Kiểm tra Trung ương Đảng Cộng sản Việt Nam ra thông báo về nội dung kỳ họp thứ 32 đề nghị cách chức các chức vụ bên Đảng Cộng sản Việt Nam của ông Nguyễn Trường Tô với lý do "sống buông thả, sinh hoạt không lành mạnh gây bất bình trong Đảng và xã hội"[5][6]